let vertex = ["A","B","C","D","E","F"]
let graph = [ //单向邻接矩阵示意图，横行ABCDEF，竖列ABCEDF
   //A B C D E F
    [0,2,4,0,0,0], //A
    [0,0,2,4,2,0], //B
    [0,0,0,0,4,0], //C
    [0,0,0,0,0,2], //D
    [0,0,0,4,0,2], //E
    [0,0,0,0,0,0], //F
]

//定义一个永远到不了的距离，表示两个节点不相连，无限远就不相连，0就表示无限近
let INF = Number.MAX_SAFE_INTEGER //最大整数上限

function dijkstra(graph,src,){
    let dist = [] //距离的基本数据
    let visited = [] //曾经访问过的节点
    let {length} = graph //邻接矩阵的节点数
    for(let i = 0; i < length; i++){ //初始化邻接矩阵中的所有节点
        dist[i] = INF //默认每个节点相距无限远
        visited[i] = false //默认每个节点都没有被访问过
    }
    dist[src] = 0 //到起始点的距离是0

    //在没有访问过的节点中找一个离起始点最近的节点
    for(let i = 0; i < length; i++){
        let u = minDistance(dist,visited) //从没有访问过的节点里面找一个最近的节点
        visited[u] = true //找到了最近节点，被访问过了，改成true

        //for循环找找还有没有更短的路径
        for(let v = 0; v < length; v++){ //先找一个节点出来，标记初始节点到该节点的距离为最短路径，然后再看看初始节点与其他节点有没有关联，
            //并且如果初始节点与其他节点有关联且短于刚刚找到的最短路径，则更新最短路径，以此重复
            if(
                !visited[v] && //没有被访问过
                graph[u][v] !==0 && //两个节点是有关联的
                dist[u] !== INF && //不能是无限远
                dist[u] + graph[u][v] < dist[v] //初始节点到这个目标节点的距离短于最近距离
            ){
                dist[v] = dist[u] + graph[u][v] //将最新找的的更短距离更新为最短路径
            }
        }
    }
    return dist
}
function minDistance(dist,visited){
    let min = INF //初始化最近距离，默认无限远，后面遇到比这个小的就替换成那个更小的值
    let minIndex = -1 //初始化最近距离的下标，默认为-1（表示不存在），如果存在则改为正整数的任意值
    for(let v = 0; v < dist.length; v++){
        if(visited[v] === false && dist[v] <= min){ //当v节点没有被访问过并且初始节点到v节点的距离小于初始化最近距离，则进行交换
            min = dist[v] //将新的最近距离赋值给min
            minIndex = v //并且记录下标
        }
    }
    return minIndex
}

const result = dijkstra(graph,0) //从A节点到各个节点的最短路径
for(let i = 0; i < result.length; i++){
    console.log(`A -> ${vertex[i]}的最短路径是:${result[i]}`)
}